/**
 * @author wangj881
 * @date 2024-12-03 9:24
 */
public class L509_2 {

    public static void main(String[] args) {
        int fib = new Solution().fib(2);
        System.out.println(fib);
    }

    static class Solution {
        public int fib(int n) {
            if (n == 0) {
                return 0;
            }
            if (n == 1) {
                return 1;
            }

            int[] dp = new int[n + 1];
            dp[0] = 0;
            dp[1] = 1;

            for (int i = 2; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }

            return dp[n];
        }
    }
}
